package arithmetic;

import org.junit.jupiter.api.Test;

/**
 * 查找数字在有序数组的位置
 *
 * @author gaojie
 * @date 2022-03-10
 */
public class SearchIndex {

    @Test
    void test() {
        assert fun(new int[]{1, 3, 5, 8}, 5) == 2;
        assert fun(new int[]{1, 3, 5, 8}, 2) == 1;
        assert fun(new int[]{1, 3, 5, 8}, 7) == 3;
        assert fun(new int[]{1, 3, 5, 8}, 9) == 4;
        assert fun(new int[]{1, 3, 5, 8}, 0) == 0;
        assert fun(new int[]{1, 3}, 2) == 1;
        assert fun(new int[]{1}, 0) == 0;
    }

    /**
     * 从数组一半的位置开始判断
     * 若相等：直接返回
     * 若大于：继续向右
     * 若小于：继续向左
     */
    int fun(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        // 1.1.若小于等于最小值，则在最左
        if (target <= nums[0]) return 0;
        // 1.2.若大于最大值，则在最右
        if (target == nums[right]) return right;
        if (target > nums[right]) return right + 1;

        while (true) {
            // 若已没有可比较的元素，则返回
            if (left >= right) {
                // 若小于或者等于这个值，则占据该位置
                if (target <= nums[left]) return left;
                // 否则在该位置的右边
                else return left + 1;
            }

            // 3.从中间的元素开始判断
            int index = (left + right) / 2;
            int num = nums[index];
            // 3.1.若值相等，表示已找到，返回下标
            if (target == num) return index;
            // 3.2.若值偏小，则向右寻找
            if (target > num) left = index + 1;
            // 3.3.若值偏小，则向左寻找
            else right = index - 1;
        }
    }

}
